import java.util.Scanner;

public class MaxSubSumOfSequence {
    public static int maxSubArraySum(int[] arr){
        if (arr == null || arr.length == 0) return 0;
        if (arr.length == 1) return arr[0];

        int N = arr.length;
        int max = Integer.MIN_VALUE;

        int[] dp = new int[N];
        dp[0] = arr[0];
        max = Math.max(max, dp[0]);
        for (int i = 1; i < N; i++) {
            dp[i] = Math.max(arr[i], arr[i] + dp[i - 1]);
            max = Math.max(max, dp[i]);
        }

        return max;
    }

    public static void main(String[] args) {
        int Max;
        int size;
        Scanner sc=new Scanner(System.in);
        System.out.println("下面请输入数组的大小");
        size=sc.nextInt();
        int []arr=new int [100];
        System.out.println("下面开始输入数组的内容：");
        for (int i=0;i<size;i++)
        {
            arr[i]=sc.nextInt();
        }
        Max=maxSubArraySum(arr);
        System.out.println("最大子序列和为："+Max);
    }
}
